【题解】[省选联考 2020 B 卷] 丁香之路

神仙题，抢个第一篇题解

题目大意：一条链上有 $n$ 个点，有 $m$ 条连接两个点的管道，所有管道必须钻一遍，求s到其他点的最短路

定义一条路径中，不走管道的那部分路径叫做自由路径。由于所有管道的长度和是固定的，那么我们要求的就是让自由路径长度最少

如果没有管道，路径肯定是从 $s$ 到 $t$ 的一条自由路径。假设现在有一条自由路径从 $A$ 到 $B$ （ $A<B$ ），有一条管道从 $C$ 到 $D$ （ $C<D$ ），考虑以下几种情况：

$A<C<B<D$ ，我们可以把路径变成 $A→C-D→B$ ，最终的自由路径变成 $A$ 到 $C$ 和 $B$ 到 $D$ 。 $C<A<D<B$ 的情况同理。
$A<C<D<B$ ，还是把路径变成 $A→C-D→B$ ，最终的自由路径还是 $A$ 到 $C$ 和 $B$ 到 $D$
$A<B<C<D$ ，直接在 $C-D$ 上加一条自由路径让它变成一个环（这里先不考虑图的连通性问题，一个环暂时可以认为是独立于其他部分存在的。连通性会在后面处理）

注意：因为是无向边，而且一条路径也可以翻转，所以方向并不重要

根据上面几种情况找规律，发现在原有的自由路径上加一条管道，相当于把管道那段区间反转。当然这只是找规律，实际上这样做是正确的，下面是证明：

可以发现每次添加管道并反转自由路径后，所有管道边和自由边维持了一个从 $s$ 到 $t$ 的欧拉路，因此这条路径一定可行。同时它一定是最短的，因为所有的自由边都没有交叉。

只不过剩下一个很严重的问题：上面所说的“欧拉路”不是真正意义上的欧拉路，因为这些路径可能还没连通呢，只是满足了欧拉路对点度数的需求。

想让这张图连通，需要把现有的已经连通的部分缩成一个点，然后在上面求最小生成树。易得让图连通需要的最小代价就是最小生成树长度和的两倍。

具体实现时，我们先处理所有管道，包括它们形成的连通块和需要的自由路径，然后枚举每个终点单独处理。求最小生成树的时候只需要加入所有必经的节点，而因为这张图中两点的距离就是数轴上距离，因此只需要加入相邻的必经点构成的边就一定能求出最小生成树。

时间复杂度 $O((m+n^2)\log)$ （ $\log$ 来自并查集和求 mst 时给边排序）。代码太丑了，就不放了。